AGC033 A - Darker and Darker

https://atcoder.jp/contests/agc033/tasks/agc033_a

提出

code: python

from collections import deque

h, w = map(int,input().split())

a = input() for _ in range(h)

black = []

for i in range(h):

for j in range(w):

if aij == "#":

black.append(i, j)

def dfs(q):

nowi, nowj = q.popleft()

# 多点スタート

for i in black:

q = deque(i)

dfs(q)

解答

code: python

from collections import deque

h, w = map(int, input().split())

grid = input() for _ in range(h)

dist = [-1 * w for _ in range(h)]

black_cells = deque()

for i in range(h):

for j in range(w):

if gridij == '#':

black_cells.append((i, j))

distij = 0

while black_cells:

nowi, nowj = black_cells.popleft()

d = distnowinowj

for i, j in ((1, 0), (0, 1), (-1, 0), (0, -1)):

nexti, nextj = nowi + i, nowj + j

if nexti < 0 or h - 1 < nexti or nextj < 0 or w - 1 < nextj or distnextinextj != -1:

continue

else:

distnextinextj = distnowinowj + 1

black_cells.append((nexti, nextj))

# print(dist)

# ..#..#

# ......

# #..#..

# ......

# .#....

# ....#.

# 2, 1, 0, 1, 1, 0], 1, 2, 1, 1, 2, 1, 0, 1, 1, 0, 1, 2, 1, 1, 2, 1, 2, 3, 1, 0, 1, 2, 1, 2, [2, 1, 2, 1, 0, 1

ans = -1

for i in range(h):

for j in range(w):

res = distij

if (res > ans):

ans = res

print(ans)

テーマ

#bfs

蟻本 2-1 迷路の最短路

メモ

【AtCoder】典型的な BFS 問題を解く【A - Darker and Darker】

AtCoder AGC 033 A - Darker and Darker (緑色, 300 点)

提出

code: python

from collections import deque

h, w = map(int,input().split())

a = list(input()) for _ in range(h)

print(a)

for i in range(h):

for j in range(w):

if i - 1 >= 0:

if ai-1j == "#":

aij = "#"

elif i + 1 <= h:

if ai+1j == "#":

aij = "#"

elif j - 1 >= 0:

if aij-1 == "#":

aij = "#"

elif j + 1 <= w:

if aij+1 == "#":

aij = "#"

print(a)